home *** CD-ROM | disk | FTP | other *** search
/ Chip: Internet / Chip Internet.iso / viewer / gsnt / source / slzwe.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-05-12  |  7.4 KB  |  240 lines
  1. /* Copyright (C) 1991, 1992 Aladdin Enterprises.  All rights reserved.
  2.  
  3. This file is part of Ghostscript.
  4.  
  5. Ghostscript is distributed in the hope that it will be useful, but
  6. WITHOUT ANY WARRANTY.  No author or distributor accepts responsibility
  7. to anyone for the consequences of using it or for whether it serves any
  8. particular purpose or works at all, unless he says so in writing.  Refer
  9. to the Ghostscript General Public License for full details.
  10.  
  11. Everyone is granted permission to copy, modify and redistribute
  12. Ghostscript, but only under the conditions described in the Ghostscript
  13. General Public License.  A copy of this license is supposed to have been
  14. given to you along with Ghostscript so you can know your rights and
  15. responsibilities.  It should be in a file named COPYING.  Among other
  16. things, the copyright notice and this notice must be preserved on all
  17. copies.  */
  18.  
  19. /* slzwe.c */
  20. /* LZW encoding filter */
  21. #include "stdio_.h"    /* includes std.h */
  22. #include "gdebug.h"
  23. #include "stream.h"
  24.  
  25. /* Imported procedures */
  26. extern int s_filter_write_flush(P1(stream *));
  27.  
  28. /********************************************************/
  29. /* LZW routines are based on:                */
  30. /* Dr. Dobbs Journal --- Oct. 1989.             */
  31. /* Article on LZW Data Compression by Mark R. Nelson     */
  32. /********************************************************/
  33.  
  34. /*
  35.  * This code implements enhancements to the LZW algorithm.
  36.  *
  37.  * At any moment during the encoding process, let S be the width of the
  38.  * output code in bits.  Let N = 1 << S.  Let M be the next code to be
  39.  * assigned; we know that N / 2 <= M < N.  The only possible codes that
  40.  * can appear in the output are 0 .. M-1.  Therefore, we can encode some
  41.  * of these with only S-1 bits.  Specifically, let D = N - M.  Then to
  42.  * output the code C (0 <= C < M):
  43.  *    If C < D, output C in S-1 bits.
  44.  *    if D <= C < N / 2, output C * 2 in S bits.
  45.  *    Otherwise (N / 2 <= C < M), output (C + N / 2 - M) * 2 + 1 in S bits.
  46.  */
  47.  
  48. /* Define the special codes */
  49. #define code_reset 256
  50. #define code_eod 257
  51. #define code_0 258            /* first assignable code */
  52.  
  53. /* ------ LZWEncode filter ------ */
  54.  
  55. typedef struct lzw_encode_s {
  56.     byte datum;            /* last byte of this code */
  57.     unsigned mark : 4;        /* (only need 1 bit) */
  58.     unsigned prefix : 12;        /* code for prefix of this code */
  59. } lzw_encode;
  60.  
  61. #define encode_max 3000        /* max # of codes, must be */
  62.                     /* > code_0 and <= 4095 */
  63. #define hash_size (encode_max  + encode_max / 4)
  64.  
  65. typedef struct lzw_encode_table_s {
  66.     lzw_encode encode[encode_max];
  67.     ushort hashed[hash_size];
  68. } lzw_encode_table;
  69.  
  70. /* Hashing function */
  71. #define encode_hash(code, chr)\
  72.   ((uint)((code) * 59 + (chr) * ((hash_size / 256) | 1)) % hash_size)
  73.  
  74. /* Export the table size */
  75. const uint s_LZWE_table_sizeof = sizeof(lzw_encode_table);
  76.  
  77. /* Internal routine to put a code onto the target stream. */
  78. /* Let S = s->state.lzw.code_size, M = s->state.lzw.next_code, N = 1 << M. */
  79. /* Relevant invariants: 9 <= S <= 12; N / 2 <= M < N; 0 <= code < M; */
  80. /* 1 <= s->state.lzw.bits_left <= 8; only the rightmost (8 - s->state.lzw.bits_left) */
  81. /* bits of s->state.lzw.bits contain valid data. */
  82. private void
  83. lzw_put_code(register stream *s, uint code)
  84. {    byte cb;
  85.     uint rep = code, size = s->state.lzw.code_size;
  86.     stream *strm = s->strm;
  87.     if ( s->state.lzw.enhanced )
  88.        {    lzw_encode *encode = s->state.lzw.encode_table->encode;
  89.         uint mcode = code;
  90.         lzw_encode *ep;
  91.         uint N = 1 << size, M = s->state.lzw.next_code;
  92.         /* Mark this code and all its prefixes. */
  93.         while ( !(ep = encode + mcode)->mark )
  94.            {    ep->mark = 1;
  95.             mcode = ep->prefix;
  96.            }
  97.         /* See if we can represent the code in S-1 bits. */
  98.         if ( code < N - M )
  99.             --size;        /* yes */
  100.         else if ( code < N / 2 )
  101.             rep <<= 1;    /* no, trailing 0 bit */
  102.         else            /* no, trailing 1 bit */
  103.             rep = (code + N / 2 - M) * 2 + 1;
  104.        }
  105.     cb = (s->bits << s->bits_left) +
  106.         (rep >> (size - s->bits_left));
  107. #ifdef DEBUG
  108. if ( gs_debug['w'] )
  109.    {    dprintf2("[w]writing 0x%x,%d", code, s->state.lzw.code_size);
  110.     if ( s->state.lzw.enhanced ) dprintf2(" -> 0x%x,%d", rep, size);
  111.     dputc('\n');
  112.    }
  113. #endif
  114.     sputc(strm, cb);
  115.     if ( (s->bits_left += 8 - size) <= 0 )
  116.        {    const byte cb1 = rep >> -s->bits_left;
  117.         sputc(strm, cb1);
  118.         s->bits_left += 8;
  119.        }
  120.     s->bits = rep;
  121. }
  122.  
  123. /* Internal routine to reset the encoding table */
  124. private void
  125. lzw_reset_encode(stream *s)
  126. {    register int c;
  127.     lzw_encode_table *table = s->state.lzw.encode_table;
  128.     lzw_put_code(s, code_reset);
  129.     s->state.lzw.next_code = code_0;
  130.     s->state.lzw.code_size = 9;
  131.     s->state.lzw.prev_code = code_eod;
  132.     for ( c = 0; c < hash_size; c++ )
  133.         table->hashed[c] = code_eod;
  134.     for ( c = 0; c < 256; c++ )
  135.        {    lzw_encode *ec = &table->encode[c];
  136.         register ushort *tc = &table->hashed[encode_hash(code_eod, c)];
  137.         while ( *tc != code_eod )
  138.           if ( ++tc == &table->hashed[hash_size] )
  139.             tc = &table->hashed[0];
  140.         *tc = c;
  141.         ec->datum = c, ec->prefix = code_eod, ec->mark = 1;
  142.        }
  143.     table->encode[code_eod].prefix = code_reset;    /* guarantee no match */
  144.     table->encode[code_eod].mark = 1;
  145.     table->encode[code_reset].mark = 1;
  146. }
  147.  
  148. /* Initialize LZWEncode filter */
  149. void
  150. s_LZWE_init(register stream *s, lzw_encode_table *table, int enhanced)
  151. {    s->bits_left = 8;
  152.     s->state.lzw.encode_table = table;
  153.     s->state.lzw.code_size = 9;        /* needed for reset code */
  154.     s->state.lzw.next_code = code_0;        /* ditto */
  155.     s->state.lzw.enhanced = enhanced;
  156.     lzw_reset_encode(s);
  157. }
  158.  
  159. /* Flush the buffer */
  160. private int
  161. s_LZWE_write_buf(register stream *s)
  162. {    register byte *p = s->cbuf;
  163.     byte *limit = s->cptr;
  164.     int code = s->state.lzw.prev_code;
  165.     lzw_encode_table *table = s->state.lzw.encode_table;
  166.     ushort *table_end = &table->hashed[hash_size];
  167.     int limit_code;
  168. #define set_limit_code()\
  169.   limit_code = (1 << s->state.lzw.code_size) - 1;\
  170.   if ( limit_code > encode_max ) limit_code = encode_max
  171.     set_limit_code();
  172.     while ( p <= limit )
  173.        {    byte c = *p;
  174.         ushort *tp;
  175.         for ( tp = &table->hashed[encode_hash(code, c)]; ; )
  176.            {    lzw_encode *ep = &table->encode[*tp];
  177.             if ( ep->prefix == code && ep->datum == c )
  178.                {    code = *tp;
  179.                 p++;
  180.                 break;
  181.                }
  182.             else if ( *tp != code_eod )
  183.                {    if ( ++tp == table_end )
  184.                   tp = &table->hashed[0]; /* wrap around */
  185.                }
  186.             else
  187.                {    /* end of recognized sequence */
  188.                 lzw_put_code(s, code);
  189.                 if ( s->state.lzw.next_code == limit_code )
  190.                    {    /* Reached power of 2 or limit. */
  191.                     /* Determine which. */
  192.                     if ( s->state.lzw.next_code == encode_max )
  193.                        {    lzw_reset_encode(s);
  194.                         set_limit_code();
  195.                         goto cx;
  196.                        }
  197.                     s->state.lzw.code_size++;
  198.                     set_limit_code();
  199.                    }
  200. #ifdef DEBUG
  201. if ( gs_debug['w'] )
  202.                 dprintf3("[w]encoding 0x%x=0x%x+%c\n",
  203.                          s->state.lzw.next_code, code, c);
  204. #endif
  205.                 *tp = s->state.lzw.next_code++;
  206.                 ep = &table->encode[*tp];
  207.                 ep->datum = c;
  208.                 ep->prefix = code;
  209.                 ep->mark = 0;
  210. cx:                code = code_eod;
  211.                 break;
  212.                }
  213.            }
  214.        }
  215.     s->state.lzw.prev_code = code;
  216.     s->cptr = s->cbuf - 1;
  217.     return 0;
  218. }
  219.  
  220. /* Close the stream */
  221. private int
  222. s_LZWE_close(register stream *s)
  223. {    (*s->procs.write_buf)(s);
  224.     if ( s->state.lzw.prev_code != code_eod )
  225.        {    lzw_put_code(s, s->state.lzw.prev_code);    /* put out final code */
  226.         /* Adjust next_code for the enhanced case. */
  227.         s->state.lzw.next_code++;
  228.        }
  229.     lzw_put_code(s, code_eod);
  230.     if ( s->bits_left < 8 )
  231.       sputc(s->strm, s->bits << s->bits_left);    /* final byte */
  232.     return s_std_close(s);
  233. }
  234.  
  235. /* Stream procedures */
  236. const stream_procs s_LZWE_procs =
  237.    {    s_std_noavailable, NULL, s_filter_write_flush, s_LZWE_close,
  238.     NULL, s_LZWE_write_buf
  239.    };
  240.